//
//  MinimumCostAnalyzer.cpp
//  RoutingEvaluator
//
//  Created by Christopher Kemsley on 4/15/12.
//  Copyright (c) 2012 iAppolopolis. All rights reserved.
//
#if defined __GNUC__ || defined __APPLE__
#include <ext/hash_map>
#else
#include <hash_map>
#endif
#include <stack>

#include "Analyzer.hpp"
#import "Node.hpp"
#import "Link.hpp"


namespace Sim {

using namespace __gnu_cxx;
using namespace std;

struct MinimumCostAnalyzer : Analyzer
{
	MinimumCostAnalyzer () : Analyzer ( "Minimum Cost" ) { }

	
	virtual void	analyze		( NodeInfoSet * nodesInfo , LinkInfoSet * linksInfo , PropertySet const & info , Output & output )
	{
		Float64		maxRange=	20 ; // 20 is the default
		info . getValue ( "maxRange" , maxRange ) ;
		
		UInteger	startNode=	1	;
		info . getValue ( "referenceNode" , startNode ) ;
		
			
		NodeSet			*	nodes	=	NodeSet :: createSetWithNodes(nodesInfo) ;
		
		std::vector<Link*>	links	=	Link :: createLinks ( linksInfo , nodes , maxRange ) ;
			
		computeMinimumCost(nodesInfo, linksInfo, maxRange, startNode, nodes, links, output );//input nodes 7 and 11
	
	output . drawNetworkTopology ( nodes , links ) ;
		}
		
	
	void computeMinimumCost(NodeInfoSet * nodeCollection , LinkInfoSet * linkCollection , Float64 maxRange , UInteger startNode , NodeSet * nodes , std::vector<Link*>	links,  Output & output  )
		{
			
			
			/*	Setup	*/
		
			//Data garnered about nodes from Dijkstra's Algorithm
			hash_map<int, int>  locationNodes;//Tracks index of nodes
			hash_map<int, int>  visitedNodes;// Need set to keep track of visited nodes. Key node, value = location
			hash_map<int, Float64>   costNodes;// Need set to keep track of visited nodes. Key = index for node, value = cost
			hash_map<int, int>   previousNodes;// Need set to keep track of visited nodes. Key = index for node, value = previousNode
			hash_map<int, int>   nodePending;//Iterates through nodes not yet visited
			hash_map<int, int>   neighborPending;//Iterates through nodes not yet visited
			hash_map<int, int>   nextHop;//Iterates through nodes not yet visited
			
			int x = 1;
			int index;
			//int neighborIndex;
			//NodeInfo * check = NULL;
			//NodeInfo * neighborNode;
			NodeInfo * src = nodeCollection -> nodeWithIdentifier ( startNode );//Source node
			NodeInfo * currentNode; //Source node
			//NodeInfo * addedNode;
			CostAlgorithm const&	algorithm	=	CostAlgorithm :: distanceSquaredCost() ;
			Float64 cost;//Used to find cost between two prospective nodes
			std::vector<NodeInfo*>::const_iterator	hereNode	=	nodeCollection->nodes().begin() ;
			std::vector<NodeInfo*>::const_iterator	endNode		=	nodeCollection->nodes().end() ;
			
			for (NodeInfo * n = *(hereNode++); hereNode <= endNode; n = *(hereNode++), x++){// Initializations
//				locationNodes.insert( pair<int, NodeInfo>(x, *n));//Index the node
				if(x == startNode){
					costNodes.insert(pair<int,Float64>(x, 0));// Cost from source to source
				}
				else if(algorithm.costOfTransmission(src, n) < (maxRange * maxRange) ){//Calculates if node is within cost range and assigns a value if it is
					cost = algorithm.costOfTransmission(src, n);
					if(cost < 1){//calculated cost less than 1
						costNodes.insert(pair<int,Float64>(x, 1));//use this for its cost
						nodePending.insert(pair<int, int>(x, 0));
						previousNodes.insert( pair<int, int>(x, x));// Previous node in optimal path from source

					}else{
						costNodes.insert(pair<int,int>(x, cost));//use this for its cost
						nodePending.insert(pair<int, int>(x, 0));//Add all nodes in graph to Q.  // All nodes in the graph are unoptimized - thus are in Q
						previousNodes.insert( pair<int, int>(x, x));// Previous node in optimal path from source

					}
				}
				else{
					costNodes.insert( pair<int,int>(x, 9999999999999));// Index of node with unknown distance
					previousNodes.insert( pair<int, int>(x, startNode));// Previous node in optimal path from source
					nodePending.insert(pair<int, int>(x, 0));//Add all nodes in graph to Q.  // All nodes in the graph are unoptimized - thus are in Q
				}
				nextHop.insert(pair<int, int>(0, 0));
			}
			currentNode = src;
			while(!nodePending.size() == 0){                      // The main loop
				index = getSmallestCost( currentNode, nodePending, costNodes, locationNodes);//find smallest cost connected node //vertex in Q with smallest distance in cost[] ;
				if(costNodes[index] == 9999999999999){
					break ;                        // all remaining vertices are inaccessible from source
				}
				visitedNodes.insert( pair<int,int>(index, 0));//remove u from Q 
				nodePending.erase(index);
				neighborPending = getNeighbors(index, nodeCollection, nodePending, maxRange);//Get neighbors of added node
				hash_map<int, int>::iterator here = neighborPending.begin();//here = neighborNode
				hash_map<int, int>::iterator end = neighborPending.end(); 
				while(here != end){          // where v has not yet been removed from Q. Neighbors. Iterate through the neighbor nodes
					cost = costNodes[index] + algorithm.costOfTransmission(nodeCollection -> nodeWithIdentifier ( index ), nodeCollection -> nodeWithIdentifier ( here->first )); // this is the alt
					int blah = here->first;
					if(cost < costNodes[here->first]){ //alt < dist[v]:{ // Relax (u,v,a)
						costNodes.erase(here->first);
						costNodes.insert(pair<int, Float64>(here->first, cost));//Will this overwrite?
						previousNodes.erase(here->first);
						previousNodes.insert(pair<int, int>(here->first, index));
						//nodePending.erase(here->first);       // Reorder v in the Queue			
					}
					here++;//increment to next neighbor node
				}
				//currentNode = nodeCollection -> nodeWithIdentifier (index);
			}//end while ;
			hash_map<int, Float64>::iterator here = costNodes.begin();//here = neighborNode
			hash_map<int, Float64>::iterator end = costNodes.end();
			//int y = here->first;
			//Float64 costs[13];
			//while(here != end){
			//	costs[here->first] = here->second;
			//	here++;
			//	 y++;
			//}
			hash_map<int, int>::iterator heret = previousNodes.begin();//here = neighborNode
			hash_map<int, int>::iterator endt = previousNodes.end();
			//int w = heret->first;
			//int previous[13];
			while(heret != endt){
				int track = heret->first;
				int tracker;
				//previous[heret->first] = heret->second;
				while(previousNodes[track] != track){
					tracker = previousNodes[track];
					track=tracker;
				}
				nextHop.erase(heret->first);
				nextHop.insert(pair<int, int>(heret->first, track));
				heret++;
				//y++;
			}
			hash_map<int, int>::iterator herer = nextHop.begin();//here = neighborNode
			hash_map<int, int>::iterator endr = nextHop.end();
			//int nextH[13];
			//while(herer != endr){
			//	nextH[herer->first] = herer->second;
			//	herer++;
			//}
			
			/*Printing*/
			int p = 1;
			output.tableOut() << "Destination" << "		"<< "Cost" << "		" << "Next Hop" ;
			while (here != end) {
				if(p == startNode){
				} else{
					output.tableOut() << "\n" << p << "		" << here->second << "		" << herer->second ;				
				}
				here++;
				herer++;
				p++;
			}
			
		}
	
	int getSmallestCost(NodeInfo * currentNode, hash_map<int, int>  nodePending, hash_map<int, Float64> costNodes, hash_map<int, int> locationNodes){	
		hash_map<int, int>::iterator here = nodePending.begin();
		hash_map<int, int>::iterator end = nodePending.end(); 
		int nodeSmallest = here->first;
		
		while(here != end){ 
			int moop = here->first;
			Float64 a = costNodes[nodeSmallest];
			Float64 b = costNodes[here->first];
			if(costNodes[nodeSmallest] > costNodes[here->first]){//Overwrites if smaller cost is found
				nodeSmallest = here->first;
			}
			here++;
		}
		return nodeSmallest;
	}
	
	hash_map<int, int> getNeighbors(int check, NodeInfoSet * nodeCollection,hash_map<int, int>  nodePending, Float64 maxRange){
		int x = 0;
		NodeInfo * current = nodeCollection -> nodeWithIdentifier ( check );
		CostAlgorithm const&	algorithm	=	CostAlgorithm :: distanceSquaredCost() ;
		hash_map<int, int> neighbors;
		hash_map<int, int>::iterator here = nodePending.begin();
		hash_map<int, int>::iterator end = nodePending.end(); 
		while (here != end) {
			int moop = here->first;
			if(algorithm.costOfTransmission(current, nodeCollection -> nodeWithIdentifier ( here->first )) < (maxRange * maxRange) ){//Calculates if node is within cost range and assigns a value if it is
				neighbors.insert(pair<int, int>(here->first,0));
			}
			here++;
			x++;
		}
		
		return neighbors;
	}
	
	/* Dijkstra 
	  for each vertex v in Graph:            // Initializations
		          dist[v] := infinity ;              // Unknown distance function from source to v
		          previous[v] := undefined ;         // Previous node in optimal path from source
		      end for ;
	      dist[source] := 0 ;                    // Distance from source to source
	      Q := the set of all nodes in Graph ;   // All nodes in the graph are unoptimized - thus are in Q
	      while Q is not empty:                  // The main loop
		          u := vertex in Q with smallest distance in dist[] ;
		          if dist[u] = infinity:
			              break ;                        // all remaining vertices are inaccessible from source
			          end if ;
	          remove u from Q ;
	          for each neighbor v of u:          // where v has not yet been removed from Q.
		              alt := dist[u] + dist_between(u, v) ;
		              if alt < dist[v]:              // Relax (u,v,a)
			                  dist[v] := alt ;
			                  previous[v] := u ;
			                  decrease-key v in Q;       // Reorder v in the Queue
			              end if ;
			          end for ;
			      end while ;
			      return dist[] ;
			  end Dijkstra.
	
	 
	 
	 void computeMinimumCost(NodeInfoSet * nodeCollection , LinkInfoSet * linkCollection , Float64 maxRange , UInteger startNode , NodeSet * nodes , std::vector<Link*>	links )
	 {
	
	//Data garnered about nodes from Dijkstra's Algorithm
	hash_map<int, NodeInfo>  locationNodes;//Tracks index of nodes
	hash_map<int, NodeInfo>  visitedNodes;// Need set to keep track of visited nodes. Key node, value = location
	hash_map<int, Float64>   costNodes;// Need set to keep track of visited nodes. Key = index for node, value = cost
	hash_map<int, NodeInfo>   previousNodes;// Need set to keep track of visited nodes. Key = index for node, value = previousNode
	hash_map<int, NodeInfo>   nodePending;//Iterates through nodes not yet visited
	hash_map<int, NodeInfo>   neighborPending;//Iterates through nodes not yet visited
	
	int x = 0;
	int index;
	//int neighborIndex;
	//NodeInfo * check = NULL;
	//NodeInfo * neighborNode;
	NodeInfo * src = nodeCollection -> nodeWithIdentifier ( startNode );//Source node
	NodeInfo * currentNode; //Source node
	CostAlgorithm const&	algorithm	=	CostAlgorithm :: distanceSquaredCost() ;
	Float64 cost;//Used to find cost between two prospective nodes
	std::vector<NodeInfo*>::const_iterator	hereNode	=	nodeCollection->nodes().begin() ;
	std::vector<NodeInfo*>::const_iterator	endNode		=	nodeCollection->nodes().end() ;
	
	for (NodeInfo * n = *(hereNode++); hereNode < endNode; n = *(hereNode++), x++){// Initializations
		//				locationNodes.insert( pair<int, NodeInfo>(x, *n));//Index the node
		if(n == src){
			costNodes.insert(pair<int,Float64>(index, 0));// Cost from source to source
		}
		else if(algorithm.costOfTransmission(src, n) < (maxRange * maxRange) ){//Calculates if node is within cost range and assigns a value if it is
			cost = algorithm.costOfTransmission(src, n);
			if(cost < 1){//calculated cost less than 1
				costNodes.insert(pair<int,Float64>(x, 1));//use this for its cost
				//						nodePending.insert(pair<int, NodeInfo>(x, *n));
			}else{
				costNodes.insert(pair<int,int>(x, cost));//use this for its cost
				//						nodePending.insert(pair<int, NodeInfo>(x, *n));//Add all nodes in graph to Q.  // All nodes in the graph are unoptimized - thus are in Q
			}
		}
		else{
			costNodes.insert( pair<int,int>(x, 9999999999999));// Index of node with unknown distance
			//					previousNodes.insert( pair<int,NodeInfo>(x, *src));// Previous node in optimal path from source
			//					nodePending.insert(pair<int, NodeInfo>(x, *n));//Add all nodes in graph to Q.  // All nodes in the graph are unoptimized - thus are in Q
		}
	}
	currentNode = src;
	while(!nodePending.size() == 0){                      // The main loop
		//				index = getSmallestCost( currentNode, nodePending, costNodes, locationNodes);//find smallest cost connected node //vertex in Q with smallest distance in cost[] ;
		if(costNodes[index] == 9999999999999){
			break ;                        // all remaining vertices are inaccessible from source
		}
		//				visitedNodes.insert( pair<int,NodeInfo>(index, locationNodes.find(index)->second));//remove u from Q 
		nodePending.erase(index);
		//				neighborPending = getNeighbors(locationNodes.find(index)->second, nodePending, maxRange);//Get neighbors of added node
		hash_map<int, NodeInfo>::iterator here = neighborPending.begin();//here = neighborNode
		hash_map<int, NodeInfo>::iterator end = neighborPending.end(); 
		while(here != end){          // where v has not yet been removed from Q. Neighbors. Iterate through the neighbor nodes
			cost = costNodes[index] + algorithm.costOfTransmission(&locationNodes.find(index)->second, &here->second); // this is the alt
			if(cost < costNodes[here->first]){ //alt < dist[v]:{ // Relax (u,v,a)
				costNodes[here->first] = cost ;//Will this overwrite?
				previousNodes.erase(here->first);
				//						previousNodes.insert(pair<int, NodeInfo>(here->first, here->second));
				nodePending.erase(here->first);       // Reorder v in the Queue			
			}
			here++;//increment to next neighbor node
		}
	}															//end while ;
}

int getSmallestCost(NodeInfo * currentNode, hash_map<int, NodeInfo>  nodePending, hash_map<int, Float64> costNodes, hash_map<int, NodeInfo> locationNodes){	
	int nodeSmallest;
	hash_map<int, NodeInfo>::iterator here = nodePending.begin();
	hash_map<int, NodeInfo>::iterator end = nodePending.end(); 
	while(here != end){ 
		if(costNodes[nodeSmallest] > costNodes[here->first]){//Overwrites if smaller cost is found
			nodeSmallest = here->first;
		}
		here++;
	}
	return nodeSmallest;
}

hash_map<int, NodeInfo> getNeighbors(NodeInfo check, hash_map<int, NodeInfo> nodePending, Float64 maxRange){
	int x = 0;
	CostAlgorithm const&	algorithm	=	CostAlgorithm :: distanceSquaredCost() ;
	hash_map<int, NodeInfo> neighbors;
	hash_map<int, NodeInfo>::iterator here = nodePending.begin();
	hash_map<int, NodeInfo>::iterator end = nodePending.end(); 
	while (here != end) {
		//			if(algorithm.costOfTransmission(&check, &here->second) < (maxRange * maxRange) ){//Calculates if node is within cost range and assigns a value if it is
		//				neighbors.insert(pair<int, NodeInfo>(x, here->second));
		//			}
		here++;
		x++;
	}
	
	//		return neighbors;
}

	 */
} ;


	
	MinimumCostAnalyzer _MinimumCostAnalyzer ;
} // namespace
